public class Main {
    public static void main(String[] args) {

        int[][] nums={{-2,-3,3},{-5,-10,1},{10,30,-5}};
        Main main = new Main();
        main.calculateMinimumHP(nums);
    }
    //最小路径和
    public int minPathSum(int[][] grid) {
        int m=grid.length;
        int n=grid[0].length;
        int[][] dp=new int[m+1][n+1];
        dp[0][1]=0;
        for(int i=1;i<=m;i++){
            dp[i][0]=Integer.MAX_VALUE;
        }
        for(int j=2;j<=n;j++){
            dp[0][j]=Integer.MAX_VALUE;
        }
        for(int i=1;i<=m;i++){
            for(int j=1;j<=n;j++){
                dp[i][j]=Math.min(dp[i-1][j],dp[i][j-1])+grid[i-1][j-1];
            }
        }
        return dp[m][n];
    }


    //地下城游戏
    public int calculateMinimumHP(int[][] dungeon) {
        int m=dungeon.length;
        int n=dungeon[0].length;
        int[][] dp=new int[m+1][n+1];
        for(int i=0;i<=m;i++){
            dp[i][n]=Integer.MAX_VALUE;
        }
        for(int j=0;j<=n;j++){
            dp[m][j]=Integer.MAX_VALUE;
        }
        //先初始化dp[i][j]的下标值
        dp[m][n-1]=dp[m-1][n]=1;
        //从后往前遍历
        for(int i=m-1;i>=0;i--){
            for(int j=n-1;j>=0;j--){
                //确保骑士走到dp[i][j]解决掉恶魔,还剩余1滴血
                dp[i][j]=Math.min(dp[i][j+1],dp[i+1][j])-dungeon[i][j];
                //这里是判断,如果存在一个特别大的血包,这里就会影响结果（导致前面就算血小于0，一个大血包也可以使血量为正）
                dp[i][j]= Math.max(dp[i][j],1);
            }
        }
        return dp[0][0];
    }
}